/*             ----> DO NOT REMOVE THE FOLLOWING NOTICE <----
 *
 *                 Copyright (c) 2014-2015 Datalight, Inc.
 *                     All Rights Reserved Worldwide.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; use version 2 of the License.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but "AS-IS," WITHOUT ANY WARRANTY; without even the implied warranty
 *  of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

/*  Businesses and individuals that for commercial or other reasons cannot
 *  comply with the terms of the GPLv2 license may obtain a commercial license
 *  before incorporating Reliance Edge into proprietary software for
 *  distribution in any form.  Visit http://www.datalight.com/reliance-edge for
 *  more information.
 */

/** @file
 *  @brief Implements the block device buffering system.
 *
 *  This module implements the block buffer cache.  It has a number of block
 *  sized buffers which are used to store data from a given block (identified
 *  by both block number and volume number: this cache is shared among all
 *  volumes).  Block buffers may be either dirty or clean.  Most I/O passes
 *  through this module.  When a buffer is needed for a block which is not in
 *  the cache, a "victim" is selected via a simple LRU scheme.
 */
#include <redfs.h>
#include <redcore.h>


#if DINDIR_POINTERS > 0U
    #define INODE_META_BUFFERS    3U /* Inode, double indirect, indirect */
#elif REDCONF_INDIRECT_POINTERS > 0U
    #define INODE_META_BUFFERS    2U /* Inode, indirect */
#elif REDCONF_DIRECT_POINTERS == INODE_ENTRIES
    #define INODE_META_BUFFERS    1U /* Inode only */
#endif

#define INODE_BUFFERS             ( INODE_META_BUFFERS + 1U ) /* Add data buffer */

#if REDCONF_IMAP_EXTERNAL == 1
    #define IMAP_BUFFERS          1U
#else
    #define IMAP_BUFFERS          0U
#endif

#if ( REDCONF_READ_ONLY == 1 ) || ( REDCONF_API_FSE == 1 )

/*  Read, write, truncate, lookup: One inode all the way down, plus imap.
 */
    #define MINIMUM_BUFFER_COUNT    ( INODE_BUFFERS + IMAP_BUFFERS )
#elif REDCONF_API_POSIX == 1
    #if REDCONF_API_POSIX_RENAME == 1
        #if REDCONF_RENAME_ATOMIC == 1

/*  Two parent directories all the way down.  Source and destination inode
 *  buffer.  One inode buffer for cyclic rename detection.  Imap.  The
 *  parent inode buffers are released before deleting the destination
 *  inode, so that does not increase the minimum.
 */
            #define MINIMUM_BUFFER_COUNT    ( INODE_BUFFERS + INODE_BUFFERS + 3U + IMAP_BUFFERS )
        #else

/*  Two parent directories all the way down.  Source inode buffer.  One
 *  inode buffer for cyclic rename detection.  Imap.
 */
            #define MINIMUM_BUFFER_COUNT    ( INODE_BUFFERS + INODE_BUFFERS + 2U + IMAP_BUFFERS )
        #endif
    #else

/*  Link/create: Needs a parent inode all the way down, an extra inode
 *  buffer, and an imap buffer.
 *
 *  Unlink is the same, since the parent inode buffers are released before
 *  the inode is deleted.
 */
        #define MINIMUM_BUFFER_COUNT    ( INODE_BUFFERS + 1U + IMAP_BUFFERS )
    #endif /* if REDCONF_API_POSIX_RENAME == 1 */
#endif /* if ( REDCONF_READ_ONLY == 1 ) || ( REDCONF_API_FSE == 1 ) */

#if REDCONF_BUFFER_COUNT < MINIMUM_BUFFER_COUNT
    #error "REDCONF_BUFFER_COUNT is too low for the configuration"
#endif


/*  A note on the typecasts in the below macros: Operands to bitwise operators
 *  are subject to the "usual arithmetic conversions".  This means that the
 *  flags, which have uint16_t values, are promoted to int.  MISRA-C:2012 R10.1
 *  forbids using signed integers in bitwise operations, so we cast to uint32_t
 *  to avoid the integer promotion, then back to uint16_t to reflect the actual
 *  type.
 */
#define BFLAG_META_MASK    ( uint16_t ) ( ( uint32_t ) BFLAG_META_MASTER | BFLAG_META_IMAP | BFLAG_META_INODE | BFLAG_META_INDIR | BFLAG_META_DINDIR )
#define BFLAG_MASK         ( uint16_t ) ( ( uint32_t ) BFLAG_DIRTY | BFLAG_NEW | BFLAG_META_MASK )


/*  An invalid block number.  Used to indicate buffers which are not currently
 *  in use.
 */
#define BBLK_INVALID    UINT32_MAX


/** @brief Metadata stored for each block buffer.
 *
 *  To make better use of CPU caching when searching the BUFFERHEAD array, this
 *  structure should be kept small.
 */
typedef struct
{
    uint32_t ulBlock;  /**< Block number the buffer is associated with; BBLK_INVALID if unused. */
    uint8_t bVolNum;   /**< Volume the block resides on. */
    uint8_t bRefCount; /**< Number of references. */
    uint16_t uFlags;   /**< Buffer flags: mask of BFLAG_* values. */
} BUFFERHEAD;


/** @brief State information for the block buffer module.
 */
typedef struct
{
    /** Number of buffers which are referenced (have a bRefCount > 0).
     */
    uint16_t uNumUsed;

    /** MRU array.  Each element of the array stores a buffer index; each buffer
     *  index appears in the array once and only once.  The first element of the
     *  array is the most-recently-used (MRU) buffer, followed by the next most
     *  recently used, and so on, till the last element, which is the least-
     *  recently-used (LRU) buffer.
     */
    uint8_t abMRU[ REDCONF_BUFFER_COUNT ];

    /** Buffer heads, storing metadata for each buffer.
     */
    BUFFERHEAD aHead[ REDCONF_BUFFER_COUNT ];

    /** Array of memory for the block buffers themselves.
     *
     *  Force 64-bit alignment of the aabBuffer array to ensure that it is safe
     *  to cast buffer pointers to node structure pointers.
     */
    ALIGNED_2D_BYTE_ARRAY( b, aabBuffer, REDCONF_BUFFER_COUNT, REDCONF_BLOCK_SIZE );
} BUFFERCTX;


static bool BufferIsValid( const uint8_t * pbBuffer,
                           uint16_t uFlags );
static bool BufferToIdx( const void * pBuffer,
                         uint8_t * pbIdx );
#if REDCONF_READ_ONLY == 0
    static REDSTATUS BufferWrite( uint8_t bIdx );
    static REDSTATUS BufferFinalize( uint8_t * pbBuffer,
                                     uint16_t uFlags );
#endif
static void BufferMakeLRU( uint8_t bIdx );
static void BufferMakeMRU( uint8_t bIdx );
static bool BufferFind( uint32_t ulBlock,
                        uint8_t * pbIdx );

#ifdef REDCONF_ENDIAN_SWAP
    static void BufferEndianSwap( const void * pBuffer,
                                  uint16_t uFlags );
    static void BufferEndianSwapHeader( NODEHEADER * pHeader );
    static void BufferEndianSwapMaster( MASTERBLOCK * pMaster );
    static void BufferEndianSwapMetaRoot( METAROOT * pMetaRoot );
    static void BufferEndianSwapInode( INODE * pInode );
    static void BufferEndianSwapIndir( INDIR * pIndir );
#endif


static BUFFERCTX gBufCtx;


/** @brief Initialize the buffers.
 */
void RedBufferInit( void )
{
    uint8_t bIdx;

    RedMemSet( &gBufCtx, 0U, sizeof( gBufCtx ) );

    for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
    {
        /*  When the buffers have been freshly initialized, acquire the buffers
         *  in the order in which they appear in the array.
         */
        gBufCtx.abMRU[ bIdx ] = ( uint8_t ) ( ( REDCONF_BUFFER_COUNT - bIdx ) - 1U );
        gBufCtx.aHead[ bIdx ].ulBlock = BBLK_INVALID;
    }
}


/** @brief Acquire a buffer.
 *
 *  @param ulBlock  Block number to acquire.
 *  @param uFlags   BFLAG_ values for the operation.
 *  @param ppBuffer On success, populated with the acquired buffer.
 *
 *  @return A negated ::REDSTATUS code indicating the operation result.
 *
 *  @retval 0           Operation was successful.
 *  @retval -RED_EIO    A disk I/O error occurred.
 *  @retval -RED_EINVAL Invalid parameters.
 *  @retval -RED_EBUSY  All buffers are referenced.
 */
REDSTATUS RedBufferGet( uint32_t ulBlock,
                        uint16_t uFlags,
                        void ** ppBuffer )
{
    REDSTATUS ret = 0;
    uint8_t bIdx;

    if( ( ulBlock >= gpRedVolume->ulBlockCount ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) || ( ppBuffer == NULL ) )
    {
        REDERROR();
        ret = -RED_EINVAL;
    }
    else
    {
        if( BufferFind( ulBlock, &bIdx ) )
        {
            /*  Error if the buffer exists and BFLAG_NEW was specified, since
             *  the new flag is used when a block is newly allocated/created, so
             *  the block was previously free and and there should never be an
             *  existing buffer for a free block.
             *
             *  Error if the buffer exists but does not have the same type as
             *  was requested.
             */
            if( ( ( uFlags & BFLAG_NEW ) != 0U ) ||
                ( ( uFlags & BFLAG_META_MASK ) != ( gBufCtx.aHead[ bIdx ].uFlags & BFLAG_META_MASK ) ) )
            {
                CRITICAL_ERROR();
                ret = -RED_EFUBAR;
            }
        }
        else if( gBufCtx.uNumUsed == REDCONF_BUFFER_COUNT )
        {
            /*  The MINIMUM_BUFFER_COUNT is supposed to ensure that no operation
             *  ever runs out of buffers, so this should never happen.
             */
            CRITICAL_ERROR();
            ret = -RED_EBUSY;
        }
        else
        {
            BUFFERHEAD * pHead;

            /*  Search for the least recently used buffer which is not
             *  referenced.
             */
            for( bIdx = ( uint8_t ) ( REDCONF_BUFFER_COUNT - 1U ); bIdx > 0U; bIdx-- )
            {
                if( gBufCtx.aHead[ gBufCtx.abMRU[ bIdx ] ].bRefCount == 0U )
                {
                    break;
                }
            }

            bIdx = gBufCtx.abMRU[ bIdx ];
            pHead = &gBufCtx.aHead[ bIdx ];

            if( pHead->bRefCount == 0U )
            {
                /*  If the LRU buffer is valid and dirty, write it out before
                 *  repurposing it.
                 */
                if( ( ( pHead->uFlags & BFLAG_DIRTY ) != 0U ) && ( pHead->ulBlock != BBLK_INVALID ) )
                {
                    #if REDCONF_READ_ONLY == 1
                        CRITICAL_ERROR();
                        ret = -RED_EFUBAR;
                    #else
                        ret = BufferWrite( bIdx );
                    #endif
                }
            }
            else
            {
                /*  All the buffers are used, which should have been caught by
                 *  checking gBufCtx.uNumUsed.
                 */
                CRITICAL_ERROR();
                ret = -RED_EBUSY;
            }

            if( ret == 0 )
            {
                if( ( uFlags & BFLAG_NEW ) == 0U )
                {
                    /*  Invalidate the LRU buffer.  If the read fails, we do not
                     *  want the buffer head to continue to refer to the old
                     *  block number, since the read, even if it fails, may have
                     *  partially overwritten the buffer data (consider the case
                     *  where block size exceeds sector size, and some but not
                     *  all of the sectors are read successfully), and if the
                     *  buffer were to be used subsequently with its partially
                     *  erroneous contents, bad things could happen.
                     */
                    pHead->ulBlock = BBLK_INVALID;

                    ret = RedIoRead( gbRedVolNum, ulBlock, 1U, gBufCtx.b.aabBuffer[ bIdx ] );

                    if( ( ret == 0 ) && ( ( uFlags & BFLAG_META ) != 0U ) )
                    {
                        if( !BufferIsValid( gBufCtx.b.aabBuffer[ bIdx ], uFlags ) )
                        {
                            /*  A corrupt metadata node is usually a critical
                             *  error.  The master block is an exception since
                             *  it might be invalid because the volume is not
                             *  mounted; that condition is expected and should
                             *  not result in an assertion.
                             */
                            CRITICAL_ASSERT( ( uFlags & BFLAG_META_MASTER ) == BFLAG_META_MASTER );
                            ret = -RED_EIO;
                        }
                    }

                    #ifdef REDCONF_ENDIAN_SWAP
                        if( ret == 0 )
                        {
                            BufferEndianSwap( gBufCtx.b.aabBuffer[ bIdx ], uFlags );
                        }
                    #endif
                }
                else
                {
                    RedMemSet( gBufCtx.b.aabBuffer[ bIdx ], 0U, REDCONF_BLOCK_SIZE );
                }
            }

            if( ret == 0 )
            {
                pHead->bVolNum = gbRedVolNum;
                pHead->ulBlock = ulBlock;
                pHead->uFlags = 0U;
            }
        }

        /*  Reference the buffer, update its flags, and promote it to MRU.  This
         *  happens both when BufferFind() found an existing buffer for the
         *  block and when the LRU buffer was repurposed to create a buffer for
         *  the block.
         */
        if( ret == 0 )
        {
            BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

            pHead->bRefCount++;

            if( pHead->bRefCount == 1U )
            {
                gBufCtx.uNumUsed++;
            }

            /*  BFLAG_NEW tells this function to zero the buffer instead of
             *  reading it from disk; it has no meaning later on, and thus is
             *  not saved.
             */
            pHead->uFlags |= ( uFlags & ( ~BFLAG_NEW ) );

            BufferMakeMRU( bIdx );

            *ppBuffer = gBufCtx.b.aabBuffer[ bIdx ];
        }
    }

    return ret;
}


/** @brief Release a buffer.
 *
 *  @param pBuffer  The buffer to release.
 */
void RedBufferPut( const void * pBuffer )
{
    uint8_t bIdx;

    if( !BufferToIdx( pBuffer, &bIdx ) )
    {
        REDERROR();
    }
    else
    {
        REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount > 0U );
        gBufCtx.aHead[ bIdx ].bRefCount--;

        if( gBufCtx.aHead[ bIdx ].bRefCount == 0U )
        {
            REDASSERT( gBufCtx.uNumUsed > 0U );
            gBufCtx.uNumUsed--;
        }
    }
}


#if REDCONF_READ_ONLY == 0

/** @brief Flush all buffers for the active volume in the given range of blocks.
 *
 *  @param ulBlockStart Starting block number to flush.
 *  @param ulBlockCount Count of blocks, starting at @p ulBlockStart, to flush.
 *                      Must not be zero.
 *
 *  @return A negated ::REDSTATUS code indicating the operation result.
 *
 *  @retval 0           Operation was successful.
 *  @retval -RED_EIO    A disk I/O error occurred.
 *  @retval -RED_EINVAL Invalid parameters.
 */
    REDSTATUS RedBufferFlush( uint32_t ulBlockStart,
                              uint32_t ulBlockCount )
    {
        REDSTATUS ret = 0;

        if( ( ulBlockStart >= gpRedVolume->ulBlockCount ) ||
            ( ( gpRedVolume->ulBlockCount - ulBlockStart ) < ulBlockCount ) ||
            ( ulBlockCount == 0U ) )
        {
            REDERROR();
            ret = -RED_EINVAL;
        }
        else
        {
            uint8_t bIdx;

            for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
            {
                BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

                if( ( pHead->bVolNum == gbRedVolNum ) &&
                    ( pHead->ulBlock != BBLK_INVALID ) &&
                    ( ( pHead->uFlags & BFLAG_DIRTY ) != 0U ) &&
                    ( pHead->ulBlock >= ulBlockStart ) &&
                    ( pHead->ulBlock < ( ulBlockStart + ulBlockCount ) ) )
                {
                    ret = BufferWrite( bIdx );

                    if( ret == 0 )
                    {
                        pHead->uFlags &= ( ~BFLAG_DIRTY );
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        return ret;
    }


/** @brief Mark a buffer dirty
 *
 *  @param pBuffer  The buffer to mark dirty.
 */
    void RedBufferDirty( const void * pBuffer )
    {
        uint8_t bIdx;

        if( !BufferToIdx( pBuffer, &bIdx ) )
        {
            REDERROR();
        }
        else
        {
            REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount > 0U );

            gBufCtx.aHead[ bIdx ].uFlags |= BFLAG_DIRTY;
        }
    }


/** @brief Branch a buffer, marking it dirty and assigning a new block number.
 *
 *  @param pBuffer      The buffer to branch.
 *  @param ulBlockNew   The new block number for the buffer.
 */
    void RedBufferBranch( const void * pBuffer,
                          uint32_t ulBlockNew )
    {
        uint8_t bIdx;

        if( !BufferToIdx( pBuffer, &bIdx ) ||
            ( ulBlockNew >= gpRedVolume->ulBlockCount ) )
        {
            REDERROR();
        }
        else
        {
            BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

            REDASSERT( pHead->bRefCount > 0U );
            REDASSERT( ( pHead->uFlags & BFLAG_DIRTY ) == 0U );

            pHead->uFlags |= BFLAG_DIRTY;
            pHead->ulBlock = ulBlockNew;
        }
    }


    #if ( REDCONF_API_POSIX == 1 ) || FORMAT_SUPPORTED

/** @brief Discard a buffer, releasing it and marking it invalid.
 *
 *  @param pBuffer  The buffer to discard.
 */
        void RedBufferDiscard( const void * pBuffer )
        {
            uint8_t bIdx;

            if( !BufferToIdx( pBuffer, &bIdx ) )
            {
                REDERROR();
            }
            else
            {
                REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount == 1U );
                REDASSERT( gBufCtx.uNumUsed > 0U );

                gBufCtx.aHead[ bIdx ].bRefCount = 0U;
                gBufCtx.aHead[ bIdx ].ulBlock = BBLK_INVALID;

                gBufCtx.uNumUsed--;

                BufferMakeLRU( bIdx );
            }
        }
    #endif /* if ( REDCONF_API_POSIX == 1 ) || FORMAT_SUPPORTED */
#endif /* REDCONF_READ_ONLY == 0 */


/** @brief Discard a range of buffers, marking them invalid.
 *
 *  @param ulBlockStart The starting block number to discard
 *  @param ulBlockCount The number of blocks, starting at @p ulBlockStart, to
 *                      discard.  Must not be zero.
 *
 *  @return A negated ::REDSTATUS code indicating the operation result.
 *
 *  @retval 0           Operation was successful.
 *  @retval -RED_EINVAL Invalid parameters.
 *  @retval -RED_EBUSY  A block in the desired range is referenced.
 */
REDSTATUS RedBufferDiscardRange( uint32_t ulBlockStart,
                                 uint32_t ulBlockCount )
{
    REDSTATUS ret = 0;

    if( ( ulBlockStart >= gpRedVolume->ulBlockCount ) ||
        ( ( gpRedVolume->ulBlockCount - ulBlockStart ) < ulBlockCount ) ||
        ( ulBlockCount == 0U ) )
    {
        REDERROR();
        ret = -RED_EINVAL;
    }
    else
    {
        uint8_t bIdx;

        for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
        {
            BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

            if( ( pHead->bVolNum == gbRedVolNum ) &&
                ( pHead->ulBlock != BBLK_INVALID ) &&
                ( pHead->ulBlock >= ulBlockStart ) &&
                ( pHead->ulBlock < ( ulBlockStart + ulBlockCount ) ) )
            {
                if( pHead->bRefCount == 0U )
                {
                    pHead->ulBlock = BBLK_INVALID;

                    BufferMakeLRU( bIdx );
                }
                else
                {
                    /*  This should never happen.  There are three general cases
                     *  when this function is used:
                     *
                     *  1) Discarding every block, as happens during unmount
                     *     and at the end of format.  There should no longer be
                     *     any referenced buffers at those points.
                     *  2) Discarding a block which has become free.  All
                     *     buffers for such blocks should be put or branched
                     *     beforehand.
                     *  3) Discarding of blocks that were just written straight
                     *     to disk, leaving stale data in the buffer.  The write
                     *     code should never reference buffers for these blocks,
                     *     since they would not be needed or used.
                     */
                    CRITICAL_ERROR();
                    ret = -RED_EBUSY;
                    break;
                }
            }
        }
    }

    return ret;
}


/** Determine whether a metadata buffer is valid.
 *
 *  This includes checking its signature, CRC, and sequence number.
 *
 *  @param pbBuffer Pointer to the metadata buffer to validate.
 *  @param uFlags   The buffer flags provided by the caller.  Used to determine
 *                  the expected signature.
 *
 *  @return Whether the metadata buffer is valid.
 *
 *  @retval true    The metadata buffer is valid.
 *  @retval false   The metadata buffer is invalid.
 */
static bool BufferIsValid( const uint8_t * pbBuffer,
                           uint16_t uFlags )
{
    bool fValid;

    if( ( pbBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
    {
        REDERROR();
        fValid = false;
    }
    else
    {
        NODEHEADER buf;
        uint16_t uMetaFlags = uFlags & BFLAG_META_MASK;

        /*  Casting pbBuffer to (NODEHEADER *) would run afoul MISRA-C:2012
         *  R11.3, so instead copy the fields out.
         */
        RedMemCpy( &buf.ulSignature, &pbBuffer[ NODEHEADER_OFFSET_SIG ], sizeof( buf.ulSignature ) );
        RedMemCpy( &buf.ulCRC, &pbBuffer[ NODEHEADER_OFFSET_CRC ], sizeof( buf.ulCRC ) );
        RedMemCpy( &buf.ullSequence, &pbBuffer[ NODEHEADER_OFFSET_SEQ ], sizeof( buf.ullSequence ) );

        #ifdef REDCONF_ENDIAN_SWAP
            buf.ulCRC = RedRev32( buf.ulCRC );
            buf.ulSignature = RedRev32( buf.ulSignature );
            buf.ullSequence = RedRev64( buf.ullSequence );
        #endif

        /*  Make sure the signature is correct for the type of metadata block
         *  requested by the caller.
         */
        switch( buf.ulSignature )
        {
            case META_SIG_MASTER:
                fValid = ( uMetaFlags == BFLAG_META_MASTER );
                break;

                #if REDCONF_IMAP_EXTERNAL == 1
                    case META_SIG_IMAP:
                        fValid = ( uMetaFlags == BFLAG_META_IMAP );
                        break;
                #endif
            case META_SIG_INODE:
                fValid = ( uMetaFlags == BFLAG_META_INODE );
                break;

                #if DINDIR_POINTERS > 0U
                    case META_SIG_DINDIR:
                        fValid = ( uMetaFlags == BFLAG_META_DINDIR );
                        break;
                #endif
                #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
                    case META_SIG_INDIR:
                        fValid = ( uMetaFlags == BFLAG_META_INDIR );
                        break;
                #endif
            default:
                fValid = false;
                break;
        }

        if( fValid )
        {
            uint32_t ulComputedCrc;

            /*  Check for disk corruption by comparing the stored CRC with one
             *  computed from the data.
             *
             *  Also check the sequence number: if it is greater than the
             *  current sequence number, the block is from a previous format
             *  or the disk is writing blocks out of order.  During mount,
             *  before the metaroots have been read, the sequence number will
             *  be unknown, and the check is skipped.
             */
            ulComputedCrc = RedCrcNode( pbBuffer );

            if( buf.ulCRC != ulComputedCrc )
            {
                fValid = false;
            }
            else if( gpRedVolume->fMounted && ( buf.ullSequence >= gpRedVolume->ullSequence ) )
            {
                fValid = false;
            }
            else
            {
                /*  Buffer is valid.  No action, fValid is already true.
                 */
            }
        }
    }

    return fValid;
}


/** @brief Derive the index of the buffer.
 *
 *  @param pBuffer  The buffer to derive the index of.
 *  @param pbIdx    On success, populated with the index of the buffer.
 *
 *  @return Boolean indicating result.
 *
 *  @retval true    Success.
 *  @retval false   Failure.  @p pBuffer is not a valid buffer pointer.
 */
static bool BufferToIdx( const void * pBuffer,
                         uint8_t * pbIdx )
{
    bool fRet = false;

    if( ( pBuffer != NULL ) && ( pbIdx != NULL ) )
    {
        uint8_t bIdx;

        /*  pBuffer should be a pointer to one of the block buffers.
         *
         *  A good compiler should optimize this loop into a bounds check and an
         *  alignment check, although GCC has been observed to not do so; if the
         *  number of buffers is small, it should not make much difference.  The
         *  alternative is to use pointer comparisons, but this both deviates
         *  from MISRA-C:2012 and involves undefined behavior.
         */
        for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
        {
            if( pBuffer == &gBufCtx.b.aabBuffer[ bIdx ][ 0U ] )
            {
                break;
            }
        }

        if( ( bIdx < REDCONF_BUFFER_COUNT ) &&
            ( gBufCtx.aHead[ bIdx ].ulBlock != BBLK_INVALID ) &&
            ( gBufCtx.aHead[ bIdx ].bVolNum == gbRedVolNum ) )
        {
            *pbIdx = bIdx;
            fRet = true;
        }
    }

    return fRet;
}


#if REDCONF_READ_ONLY == 0

/** @brief Write out a dirty buffer.
 *
 *  @param bIdx The index of the buffer to write.
 *
 *  @return A negated ::REDSTATUS code indicating the operation result.
 *
 *  @retval 0           Operation was successful.
 *  @retval -RED_EIO    A disk I/O error occurred.
 *  @retval -RED_EINVAL Invalid parameters.
 */
    static REDSTATUS BufferWrite( uint8_t bIdx )
    {
        REDSTATUS ret = 0;

        if( bIdx < REDCONF_BUFFER_COUNT )
        {
            const BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

            REDASSERT( ( pHead->uFlags & BFLAG_DIRTY ) != 0U );

            if( ( pHead->uFlags & BFLAG_META ) != 0U )
            {
                ret = BufferFinalize( gBufCtx.b.aabBuffer[ bIdx ], pHead->uFlags );
            }

            if( ret == 0 )
            {
                ret = RedIoWrite( pHead->bVolNum, pHead->ulBlock, 1U, gBufCtx.b.aabBuffer[ bIdx ] );

                #ifdef REDCONF_ENDIAN_SWAP
                    BufferEndianSwap( gBufCtx.b.aabBuffer[ bIdx ], pHead->uFlags );
                #endif
            }
        }
        else
        {
            REDERROR();
            ret = -RED_EINVAL;
        }

        return ret;
    }


/** @brief Finalize a metadata buffer.
 *
 *  This updates the CRC and the sequence number.  It also sets the signature,
 *  though this is only truly needed if the buffer is new.
 *
 *  @param pbBuffer Pointer to the metadata buffer to finalize.
 *  @param uFlags   The associated buffer flags.  Used to determine the expected
 *                  signature.
 *
 *  @return A negated ::REDSTATUS code indicating the operation result.
 *
 *  @retval 0           Operation was successful.
 *  @retval -RED_EINVAL Invalid parameter; or maximum sequence number reached.
 */
    static REDSTATUS BufferFinalize( uint8_t * pbBuffer,
                                     uint16_t uFlags )
    {
        REDSTATUS ret = 0;

        if( ( pbBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
        {
            REDERROR();
            ret = -RED_EINVAL;
        }
        else
        {
            uint32_t ulSignature;

            switch( uFlags & BFLAG_META_MASK )
            {
                case BFLAG_META_MASTER:
                    ulSignature = META_SIG_MASTER;
                    break;

                    #if REDCONF_IMAP_EXTERNAL == 1
                        case BFLAG_META_IMAP:
                            ulSignature = META_SIG_IMAP;
                            break;
                    #endif
                case BFLAG_META_INODE:
                    ulSignature = META_SIG_INODE;
                    break;

                    #if DINDIR_POINTERS > 0U
                        case BFLAG_META_DINDIR:
                            ulSignature = META_SIG_DINDIR;
                            break;
                    #endif
                    #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
                        case BFLAG_META_INDIR:
                            ulSignature = META_SIG_INDIR;
                            break;
                    #endif
                default:
                    ulSignature = 0U;
                    break;
            }

            if( ulSignature == 0U )
            {
                REDERROR();
                ret = -RED_EINVAL;
            }
            else
            {
                uint64_t ullSeqNum = gpRedVolume->ullSequence;

                ret = RedVolSeqNumIncrement();

                if( ret == 0 )
                {
                    uint32_t ulCrc;

                    RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_SIG ], &ulSignature, sizeof( ulSignature ) );
                    RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_SEQ ], &ullSeqNum, sizeof( ullSeqNum ) );

                    #ifdef REDCONF_ENDIAN_SWAP
                        BufferEndianSwap( pbBuffer, uFlags );
                    #endif

                    ulCrc = RedCrcNode( pbBuffer );
                    #ifdef REDCONF_ENDIAN_SWAP
                        ulCrc = RedRev32( ulCrc );
                    #endif
                    RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_CRC ], &ulCrc, sizeof( ulCrc ) );
                }
            }
        }

        return ret;
    }
#endif /* REDCONF_READ_ONLY == 0 */


#ifdef REDCONF_ENDIAN_SWAP

/** @brief Swap the byte order of a metadata buffer
 *
 *  Does nothing if the buffer is not a metadata node.  Also does nothing for
 *  meta roots, which don't go through the buffers anyways.
 *
 *  @param pBuffer  Pointer to the metadata buffer to swap
 *  @param uFlags   The associated buffer flags.  Used to determin the type of
 *                  metadata node.
 */
    static void BufferEndianSwap( void * pBuffer,
                                  uint16_t uFlags )
    {
        if( ( pBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
        {
            REDERROR();
        }
        else if( ( uFlags & BFLAG_META_MASK ) != 0 )
        {
            BufferEndianSwapHeader( pBuffer );

            switch( uFlags & BFLAG_META_MASK )
            {
                case BFLAG_META_MASTER:
                    BufferEndianSwapMaster( pBuffer );
                    break;

                case BFLAG_META_INODE:
                    BufferEndianSwapInode( pBuffer );
                    break;

                    #if DINDIR_POINTERS > 0U
                        case BFLAG_META_DINDIR:
                            BufferEndianSwapIndir( pBuffer );
                            break;
                    #endif
                    #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
                        case BFLAG_META_INDIR:
                            BufferEndianSwapIndir( pBuffer );
                            break;
                    #endif
                default:
                    break;
            }
        }
        else
        {
            /*  File data buffers do not need to be swapped.
             */
        }
    }


/** @brief Swap the byte order of a metadata node header
 *
 *  @param pHeader  Pointer to the metadata node header to swap
 */
    static void BufferEndianSwapHeader( NODEHEADER * pHeader )
    {
        if( pHeader == NULL )
        {
            REDERROR();
        }
        else
        {
            pHeader->ulSignature = RedRev32( pHeader->ulSignature );
            pHeader->ulCRC = RedRev32( pHeader->ulCRC );
            pHeader->ullSequence = RedRev64( pHeader->ullSequence );
        }
    }


/** @brief Swap the byte order of a master block
 *
 *  @param pMaster  Pointer to the master block to swap
 */
    static void BufferEndianSwapMaster( MASTERBLOCK * pMaster )
    {
        if( pMaster == NULL )
        {
            REDERROR();
        }
        else
        {
            pMaster->ulVersion = RedRev32( pMaster->ulVersion );
            pMaster->ulFormatTime = RedRev32( pMaster->ulFormatTime );
            pMaster->ulInodeCount = RedRev32( pMaster->ulInodeCount );
            pMaster->ulBlockCount = RedRev32( pMaster->ulBlockCount );
            pMaster->uMaxNameLen = RedRev16( pMaster->uMaxNameLen );
            pMaster->uDirectPointers = RedRev16( pMaster->uDirectPointers );
            pMaster->uIndirectPointers = RedRev16( pMaster->uIndirectPointers );
        }
    }


/** @brief Swap the byte order of an inode
 *
 *  @param pInode   Pointer to the inode to swap
 */
    static void BufferEndianSwapInode( INODE * pInode )
    {
        if( pInode == NULL )
        {
            REDERROR();
        }
        else
        {
            uint32_t ulIdx;

            pInode->ullSize = RedRev64( pInode->ullSize );

            #if REDCONF_INODE_BLOCKS == 1
                pInode->ulBlocks = RedRev32( pInode->ulBlocks );
            #endif

            #if REDCONF_INODE_TIMESTAMPS == 1
                pInode->ulATime = RedRev32( pInode->ulATime );
                pInode->ulMTime = RedRev32( pInode->ulMTime );
                pInode->ulCTime = RedRev32( pInode->ulCTime );
            #endif

            pInode->uMode = RedRev16( pInode->uMode );

            #if ( REDCONF_API_POSIX == 1 ) && ( REDCONF_API_POSIX_LINK == 1 )
                pInode->uNLink = RedRev16( pInode->uNLink );
            #endif

            #if REDCONF_API_POSIX == 1
                pInode->ulPInode = RedRev32( pInode->ulPInode );
            #endif

            for( ulIdx = 0; ulIdx < INODE_ENTRIES; ulIdx++ )
            {
                pInode->aulEntries[ ulIdx ] = RedRev32( pInode->aulEntries[ ulIdx ] );
            }
        }
    }


    #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES

/** @brief Swap the byte order of an indirect or double indirect node
 *
 *  @param pIndir   Pointer to the node to swap
 */
        static void BufferEndianSwapIndir( INDIR * pIndir )
        {
            if( pIndir == NULL )
            {
                REDERROR();
            }
            else
            {
                uint32_t ulIdx;

                pIndir->ulInode = RedRev32( pIndir->ulInode );

                for( ulIdx = 0; ulIdx < INDIR_ENTRIES; ulIdx++ )
                {
                    pIndir->aulEntries[ ulIdx ] = RedRev32( pIndir->aulEntries[ ulIdx ] );
                }
            }
        }

    #endif /* REDCONF_DIRECT_POINTERS < INODE_ENTRIES */
#endif /* #ifdef REDCONF_ENDIAN_SWAP */


/** @brief Mark a buffer as least recently used.
 *
 *  @param bIdx The index of the buffer to make LRU.
 */
static void BufferMakeLRU( uint8_t bIdx )
{
    if( bIdx >= REDCONF_BUFFER_COUNT )
    {
        REDERROR();
    }
    else if( bIdx != gBufCtx.abMRU[ REDCONF_BUFFER_COUNT - 1U ] )
    {
        uint8_t bMruIdx;

        /*  Find the current position of the buffer in the MRU array.  We do not
         *  need to check the last slot, since we already know from the above
         *  check that the index is not there.
         */
        for( bMruIdx = 0U; bMruIdx < ( REDCONF_BUFFER_COUNT - 1U ); bMruIdx++ )
        {
            if( bIdx == gBufCtx.abMRU[ bMruIdx ] )
            {
                break;
            }
        }

        if( bMruIdx < ( REDCONF_BUFFER_COUNT - 1U ) )
        {
            /*  Move the buffer index to the back of the MRU array, making it
             *  the LRU buffer.
             */
            RedMemMove( &gBufCtx.abMRU[ bMruIdx ], &gBufCtx.abMRU[ bMruIdx + 1U ], REDCONF_BUFFER_COUNT - ( ( uint32_t ) bMruIdx + 1U ) );
            gBufCtx.abMRU[ REDCONF_BUFFER_COUNT - 1U ] = bIdx;
        }
        else
        {
            REDERROR();
        }
    }
    else
    {
        /*  Buffer already LRU, nothing to do.
         */
    }
}


/** @brief Mark a buffer as most recently used.
 *
 *  @param bIdx The index of the buffer to make MRU.
 */
static void BufferMakeMRU( uint8_t bIdx )
{
    if( bIdx >= REDCONF_BUFFER_COUNT )
    {
        REDERROR();
    }
    else if( bIdx != gBufCtx.abMRU[ 0U ] )
    {
        uint8_t bMruIdx;

        /*  Find the current position of the buffer in the MRU array.  We do not
         *  need to check the first slot, since we already know from the above
         *  check that the index is not there.
         */
        for( bMruIdx = 1U; bMruIdx < REDCONF_BUFFER_COUNT; bMruIdx++ )
        {
            if( bIdx == gBufCtx.abMRU[ bMruIdx ] )
            {
                break;
            }
        }

        if( bMruIdx < REDCONF_BUFFER_COUNT )
        {
            /*  Move the buffer index to the front of the MRU array, making it
             *  the MRU buffer.
             */
            RedMemMove( &gBufCtx.abMRU[ 1U ], &gBufCtx.abMRU[ 0U ], bMruIdx );
            gBufCtx.abMRU[ 0U ] = bIdx;
        }
        else
        {
            REDERROR();
        }
    }
    else
    {
        /*  Buffer already MRU, nothing to do.
         */
    }
}


/** @brief Find a block in the buffers.
 *
 *  @param ulBlock  The block number to find.
 *  @param pbIdx    If the block is buffered (true is returned), populated with
 *                  the index of the buffer.
 *
 *  @return Boolean indicating whether or not the block is buffered.
 *
 *  @retval true    @p ulBlock is buffered, and its index has been stored in
 *                  @p pbIdx.
 *  @retval false   @p ulBlock is not buffered.
 */
static bool BufferFind( uint32_t ulBlock,
                        uint8_t * pbIdx )
{
    bool ret = false;

    if( ( ulBlock >= gpRedVolume->ulBlockCount ) || ( pbIdx == NULL ) )
    {
        REDERROR();
    }
    else
    {
        uint8_t bIdx;

        for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
        {
            const BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];

            if( ( pHead->bVolNum == gbRedVolNum ) && ( pHead->ulBlock == ulBlock ) )
            {
                *pbIdx = bIdx;
                ret = true;
                break;
            }
        }
    }

    return ret;
}
